/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/decode-ways-ii
   @Language: C++
   @Datetime: 19-05-30 10:43
   */

class Solution {
public:
	/**
	 * @param s: a message being encoded
	 * @return: an integer
	 */
	int numDecodings(string &s) {
		// write your code here
		if(s.length()==0 || s.find("00")!=s.npos) return 0;
		long pp=0, p=0, cur=1;
		for(int i=0; i<s.length(); ++i){
			pp=p, p=cur, cur=0;
			if(s[i]=='*'){
				cur=9*p;
				if(i>0){
					if(s[i-1]=='*') cur+=15*pp;
					else if(s[i-1]=='1') cur+=9*pp;
					else if(s[i-1]=='2') cur+=6*pp;
				}
			}
			else if(s[i]=='0'){
				if(i==0) return 0;
				if(s[i-1]=='1' || s[i-1]=='2') cur+=pp;
				else if(s[i-1]=='*') cur+=2*pp;
				else if(s[i-1]>'2') return 0;
			}
			else if(s[i]>'0') {
				cur=p;
				if(i>0){
					if(s[i-1]=='*'){
						if(s[i]>='0' && s[i]<='6') cur+=2*pp;
						if(s[i]>'6' && s[i]<='9') cur+=pp;
					}
					else{
						const int num=(s[i-1]-'0')*10+s[i]-'0';
						if(num>9 && num<27) cur+=pp;
					}
				}
			}
			cur%=(long)1e9+7;
		}
		return cur;
	}
};
